from typing import List


class DisjointSetUnion:
    def __init__(self, n):
        self.n = self.rank = [1] * n
        self.f = list(range(n))

    def find(self, x):
        if self.f[x] == x:
            return x
        self.f[x] = self.find(self.f[x])
        return self.f[x]

    def union_set(self, x, y):
        fx = self.find(x)
        fy = self.find(y)

        if fx == fy:  # 已经连接的点
            return False

        if self.rank[fx] < self.rank[fy]:
            fx, fy = fy, fx  # 确保 fx为比较复杂的数
        self.rank[fx] += self.rank[fy]
        self.f[fy] = fx

        return True


class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        edges = []
        n = len(points)
        for i in range(len(points)):
            for j in range(i + 1, len(points)):
                long = abs(points[i][0] - points[j][0]) + abs(
                    points[i][1] - points[j][1]
                )
                edges.append((long, i, j))
        edges.sort()
        print(edges)

        dsu = DisjointSetUnion(n)
        res, num = 0, 1

        for length, x, y in edges:
            if dsu.union_set(x, y):
                res += length
                num += 1
                if num == n:
                    break
        return res


if __name__ == "__main__":
    res = Solution().minCostConnectPoints([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]])
    print(res)

